package sit.engreal.leetcode.problems100;

import org.junit.jupiter.api.Assertions;

/**
 * <a herf="https://leetcode.cn/problems/longest-palindromic-substring/">5. 最长回文子串</a>
 */
public class LeetCode5 {
    public static class Solution {
        public String longestPalindrome(String s) {
            if (s.isEmpty()) {
                return "";
            }
            int begin = 0;
            int end = 1;
            for (int i = 0; i < s.length() - 1; i++) {
                int left = i - 1;
                int right = i + 1;
                while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                    left--;
                    right++;
                }
                int len = right - left - 1;
                if ((end - begin) < len) {
                    begin = left + 1;
                    end = right;
                }

                left = i;
                right = i + 1;
                while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                    left--;
                    right++;
                }
                len = right - left - 1;
                if ((end - begin) < len) {
                    begin = left + 1;
                    end = right;
                }

            }
            return s.substring(begin, end);
        }

        public static void main(String[] args) {
            final Solution solution = new Solution();
            Assertions.assertEquals("bab", solution.longestPalindrome("babad"));
            Assertions.assertEquals("bb", solution.longestPalindrome("cbbd"));
        }
    }
}
